import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;


public class Ex6_1 {
	
	
	public static void main(String[] args) {
		
		
	 /*	DPCHANGE(money, coins)
	     MinNumCoins(0) ← 0
	     for m ← 1 to money
	            MinNumCoins(m) ← ∞
	            for i ← 1 to |coins|
	                if m ≥ coini
	                    if MinNumCoins(m - coini) + 1 < MinNumCoins(m)
	                        MinNumCoins(m) ← MinNumCoins(m - coini) + 1
	        output MinNumCoins(money)
		*/
		Integer money = 19315;
		ArrayList<Integer> coins = 
					readCoins("C:\\Users\\josemfer\\Downloads\\ex6_1_coins.txt");
		HashMap<Integer,Integer> minNumCoins = new HashMap<Integer,Integer>();
		minNumCoins.put(0, 0);
		for (int m = 1;m<=money;m++) {
			minNumCoins.put(m, 1000000000);
			for (int i=0;i<coins.size();i++) {
				if (m >= coins.get(i)) {
					if (minNumCoins.get(m-coins.get(i))+1 < minNumCoins.get(m)) {
						minNumCoins.put(m,   minNumCoins.get(m - coins.get(i)) + 1   );
					}
				}
			}
		}
		
		System.out.println(minNumCoins.get(money));
					
	}
	
	public static ArrayList<Integer> readCoins(String file) {
		ArrayList<Integer> coins = new ArrayList<Integer>();
		try {
			String inputFile = KmerCounter.readFile(file);
			for (String s : inputFile.split(",")) {
				Integer coin = Integer.valueOf(s);
				coins.add(coin);
			}

		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
		return coins;		
	}
	

}
